'''
Created on 19/11/2012

@author: greis
'''
from util import util

class Search:
    """
    Search define the parameters need by the search methods
    """

    def depthFirstSearch(self, iniState, endState, state):
        """
        Search the deepest nodes in the search tree first
        return a list of actions to change from iniState to endState
        Example usage: depthFirstSearch( iniState, endState, state)
        Example return: [Action1, Action2]
        """
        "*** YOUR CODE HERE ***"
        gameState = state
        currState=iniState
        if gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState): 
            return []
        else:
            closedSet=set()
            fringe=util.Stack()
            fringe.push((currState,[]))
            while not fringe.isEmpty():
                currState,path=fringe.pop()
                if gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState):
                    return path
                elif currState in closedSet:
                    continue       
                else:
                    closedSet.add(currState)
                    for currState,nextAction in currState.getLegalActionsToStates():
                        childNode = (currState, path + [nextAction])
                        fringe.push(childNode)
                        
    def breadthFirstSearch(self, iniState, endState, state):
        """
        Search the shallowest nodes in the search tree first.
        return a list of actions to change from iniState to endState
        Example usage: depthFirstSearch( iniState, endState, state)
        Example return: [Action1, Action2]
        """
        "*** YOUR CODE HERE ***"
        gameState = state
        currState=iniState
        if gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState): 
            return []
        else:
            closedSet=set()
            fringe=util.Queue()
            fringe.push((currState,[]))
            while not fringe.isEmpty():
                currState,path=fringe.pop()
                if gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState):
                    return path
                elif currState in closedSet:
                    continue       
                else:
                    closedSet.add(currState)
                    for currState,nextAction in currState.getLegalActionsToStates():
                        childNode = (currState, path + [nextAction])
                        fringe.push(childNode)
                        
    def uniformCostSearch(self, iniState, endState, state):
        """
        Search the node of least total cost first.
        return a list of actions to change from iniState to endState
        Example usage: depthFirstSearch( iniState, endState, state)
        Example return: [Action1, Action2]
        """
        "*** YOUR CODE HERE ***"
        gameState = state
        currState=iniState
        if gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState): 
            return []
        else:
            closedSet=set()
            fringe=util.PriorityQueue()
            fringe.push((currState,[],0),0)
            while not fringe.isEmpty():
                currState,path,cost=fringe.pop()
                if gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState):
                    return path
                elif currState in closedSet:
                    continue       
                else:
                    closedSet.add(currState)
                    for currState,nextAction in currState.getLegalActionsToStates():
                        nextCost = currState.getCostOfActions([nextAction])
                        childNode = (currState, path + [nextAction],cost + nextCost)
                        fringe.push(childNode,cost + nextCost)

    def aStarSearch(self, iniState, endState, state, heuristicFunction):
        """
        Search the node that has the lowest combined cost and heuristic first.
        return a list of actions to change from iniState to endState
        Example usage: depthFirstSearch( iniState, endState, state)
        Example return: [Action1, Action2]
        """
        "*** YOUR CODE HERE ***"
        gameState = state
        if heuristicFunction:
            heuristic = heuristicFunction
        else:
            heuristic = state.basicHeuristicFunction
        currState=iniState
        if gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState): 
            return []
        else:
            closedSet=set()
            fringe=util.PriorityQueue()
            fringe.push((currState,[]),0+heuristic(gameState))
            while not fringe.isEmpty():
                currState,path=fringe.pop()
                if gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState):
                    return path
                elif currState in closedSet:
                    continue       
                else:
                    closedSet.add(currState)
                    for currState,nextAction in currState.getLegalActionsToStates():
                        nextCost = currState.getCostOfActions([nextAction])
                        nextHeuristic = heuristic(gameState)
                        childNode = (currState, path + [nextAction])
                        fringe.push(childNode, nextCost + nextHeuristic)
                        
    def genericSearchFringed(self, problem, fringe, searchtype, iniState, heuristicValue=(lambda x:0), endState):
        """
        Generic search method
        """
        gameState = iniState
        currentState=gameState
        if problem.isGoalState(currentState) or gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState):
            return []
        else:
            closedSet=set()
            node = (currentState,[])
            if searchtype == 2:
                fringe.push(node,0+heuristicValue(currentState))
            else:
                fringe.push(node)
            while not fringe.isEmpty():
                currentState,path=fringe.pop()
                if problem.isGoalState(currentState) or gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState):
                    return path
                elif currentState in closedSet:
                    continue       
                else:
                    closedSet.add(currentState)
                    for nextState,nextMove,nextCost in problem.getSuccessors(currentState):
                        childNode = (nextState, path + [nextMove])
                        if searchtype == 2:
                            fringe.push(childNode,problem.getCostOfActions(path + [nextMove]) + heuristicValue(nextState))
                        else:
                            fringe.push(childNode)

    def genericSearch(self, problem, fringe, searchtype, iniState, heuristicValue=(lambda x:0), endState):
        """
        Generic search method
        """
        gameState = iniState
        currentState=gameState
        linkedList = {(currentState):({},None,currentState,None,0,0)}
        if problem.isGoalState(currentState) or gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState):
            return []
        else:
            closedSet=set()
            node = currentState
            if searchtype == 2:
                fringe.push(node,0+heuristicValue(currentState))
            else:
                fringe.push(node)
            while not fringe.isEmpty():
                currentState=fringe.pop()
                if problem.isGoalState(currentState) or gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState):
                    path = self.pathBuilder(linkedList,currentState,[])
                    path.reverse()
                    return path
                elif currentState in closedSet:
                    continue       
                else:
                    closedSet.add(currentState)
                    for nextState,nextMove,nextCost in problem.getSuccessors(currentState):
                        cumulativeCost = nextCost+heuristicValue(nextState)
                        linkedList[nextState] = ({(currentState):linkedList[currentState]},currentState,nextState,nextMove,cumulativeCost,nextCost)
                        if searchtype == 2:
                            fringe.push(nextState,cumulativeCost)
                        else:
                            fringe.push(nextState)
                            
    def pathBuilder(self, linkedList, node, path):
        if node in linkedList:
            (childList,parent,nextState,action,cumulativeCost,nextCost) = linkedList.pop(node)
            if action <> None:
                path.append(action)
            self.pathBuilder(childList, parent, path)
        else:
            return path
        return path
                            
    def genericSearchNew(self, problem, fringe, searchtype, iniState, heuristicValue=(lambda x:0), endState):
        """
        Generic search method
        """
        gameState = iniState
        currentState=gameState
        linkedIndex = 0
        node = (currentState, 'SStart', 0, 0, 0, 0)
        linkedList = {(linkedIndex):node}
        if problem.isGoalState(currentState) or gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState):
            return []
        else:
            closedSet=set()
            if searchtype == 2:
                fringe.push(currentState,0+heuristicValue(currentState))
            else:
                fringe.push(currentState)
            while not fringe.isEmpty():
                currentState=fringe.pop()
                if problem.isGoalState(currentState) or gameState.isGoodState() or gameState.isBadState() or gameState.isTerminalState() or iniState.compareState(endState):
                    node = (currentState, linkedList[linkedIndex][1], linkedList[linkedIndex][-4], linkedList[linkedIndex][-3], linkedIndex, linkedList[linkedIndex][-1])
                    return self.pathBuilderNew(linkedList,node)
                elif currentState in closedSet:
                    continue       
                else:
                    closedSet.add(currentState)
                    parentIndex = linkedIndex
                    for nextState,nextMove,nextCost in problem.getSuccessors(currentState):
                        cumulativeCost = nextCost+heuristicValue(nextState)
                        linkedIndex += 1
                        node = (nextState, nextMove, nextCost, cumulativeCost, linkedIndex, parentIndex)
                        linkedList[linkedIndex] = node 
                        if searchtype == 2:
                            fringe.push(nextState,cumulativeCost)
                        else:
                            fringe.push(nextState)
    
    def pathBuilderNew(self, linkedList, node, tree=[], path=[]):
        """
        (currentState ,currentState,nextState,nextMove,cumulativeCost,nextCost)
        node[-1] is parent node key, node[-2] is current node key, node[-3] is cumulative cost, node[-4] is stepcost, node[1] is the action taken, node[0] is the current state
        """
        if not linkedList[node[-1]] in tree:
            tree.append(linkedList[node[-1]])
            path.append(node[1])
            return self.pathBuilderNew(linkedList, linkedList[node[-1]], tree, path)
        else:
            path.reverse()
            return path
    
    def depthFirstGenericSearch(self, problem, iniState, endState=None):
        """
        Search the deepest nodes in the search tree first
        return a list of actions to change from iniState to endState
        Example usage: depthFirstGenericSearch(problem, iniState, endState)
        Example return: [Action1, Action2]
        """
        return self.genericSearch(problem, util.Stack(), 1, iniState, (lambda x: 0), endState);
    
    def breadthFirstGenericSearch(self, problem, iniState, endState=None):
        """
        Search the shallowest nodes in the search tree first.
        return a list of actions to change from iniState to endState
        Example usage: breadthFirstGenericSearch(problem, iniState, endState)
        Example return: [Action1, Action2]
        """
        return self.genericSearch(problem, util.Queue(), 1, iniState, (lambda x: 0), endState);
    
    def uniformCostGenericSearch(self, problem, iniState, endState=None):
        """
        Search the node of least total cost first.
        return a list of actions to change from iniState to endState
        Example usage: uniformCostGenericSearch(problem, iniState, endState)
        Example return: [Action1, Action2]
        """
        return self.genericSearch(problem, util.PriorityQueue(), 2, iniState, (lambda x: 0), endState);
    
    def aStarGenericSearch(self, problem, iniState, heuristic=heuristicFunction, endState=None):
        """
        Search the node that has the lowest combined cost and heuristic first.
        return a list of actions to change from iniState to endState
        Example usage: aStarGenericSearch(problem, iniState, heuristic, endState)
        Example return: [Action1, Action2]
        """
        return self.genericSearch(problem, util.PriorityQueue(), 2, iniState, (lambda x: heuristic(x,problem)), endState); 

    def heuristicFunction(self, state, problem):
        """
        A heuristic function estimates the cost from the current state to the nearest
        goal in the provided SearchProblem.  This heuristic is trivial.
        """
        return 0

    def nullHeuristic(self, state, problem=None):
        """
        A heuristic function estimates the cost from the current state to the nearest
        goal in the provided SearchProblem.  This heuristic is trivial.
        """
        return 0


